package BackTracking;

import java.lang.reflect.Array;
import java.util.*;

public class combinationSum {
    private int[] candidates;

    private int target;

    public static void main(String[] args) {
        int[] candidates = {2, 3, 7};
        int target = 18;
        System.out.println(new combinationSum().combinationSumI(candidates, target));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return res;
        }
        int length = candidates.length;
        List<Integer> curRes = new ArrayList<>();
        Set<List<Integer>> tempRes = new HashSet<>();
        Arrays.sort(candidates);
        this.candidates = candidates;
        this.target = target;
        for (int i = 1; i <= target/candidates[0]; i++) {
            backTracking(tempRes, curRes, i);
        }
        res = new ArrayList<>(tempRes);
        return res;
    }

    /**
     * 方法一：利用序列长度作为限制，通过求和来判断条件
     * @param res 总结果
     * @param curRes 上一次运行的序列
     * @param length 序列最长长度限制
     */
    private void backTracking(Set<List<Integer>> res, List<Integer> curRes, int length) {
//      这可能会引入问题
        if (curRes.size() == length) {
            if (curRes.stream().reduce(Integer::sum).orElse(null) == target) {
                Collections.sort(curRes);
                res.add(new ArrayList<>(curRes));
            }
            return;
        }
        for (int i = 0; i < candidates.length; i++) {
            curRes.add(candidates[i]);
            backTracking(res, curRes, length);
            curRes.remove(curRes.size() - 1);
        }
    }

    public List<List<Integer>> combinationSumI(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
//        if (candidates == null || candidates.length == 0) {
//            return res;
//        }
//        this.candidates = candidates;
        Arrays.sort(candidates);
        backTrackingI(new ArrayList<>(), res, new boolean[candidates.length], 0, target, candidates);
        return res;
    }

    /**
     * 方法二： 通过将求和问题转化为求差==0的问题进行回溯
     * @param curRes 上一次的序列
     * @param res 存储结果
     * @param hasVisited 已经访问过的元素列表，用于剪枝
     * @param start 开始索引，用于控制开始进行计算的点
     * @param target 目标值，也就是总目标-目前和
     * @param candidates 坐标，无需放在这里
     */
    private void backTrackingI(List<Integer> curRes, List<List<Integer>> res, boolean[] hasVisited, int start, int target, int[] candidates) {
        if (target == 0) {
            res.add(new ArrayList<>(curRes));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i != 0 && candidates[i] == candidates[i-1] && !hasVisited[i - 1]) {
                continue;
            }
            if (candidates[i] <= target) {
                curRes.add(candidates[i]);
                hasVisited[i] = true;
                backTrackingI(curRes, res, hasVisited, i, target - candidates[i], candidates);
                hasVisited[i] = false;
                curRes.remove(curRes.size() - 1);
            }
        }
    }


}
